1. Field of the Invention
The invention is related to a pattern matching technique for high throughput network processing.
2. Description of the Related Art
(Note: This application references a number of different publications as indicated throughout the specification by one or more reference numbers within brackets, e. g., [x]. A list of these different publications and patents ordered according to these reference numbers can be found below in the section entitled “References.” Each of these publications and patents is incorporated by reference herein.)
Pattern matching is one of the most fundamental operations that modern network devices (such as routers, access points, intrusion detection systems, etc.) need to perform at high speed. For example, Internet Protocol (IP)-forwarding requires longest-prefix matching, packet classification requires multidimensional range queries, and intrusion detection requires high speed string matching. The amount of network traffic seen by a router is already on the order of tens of gigabits per second, and keeping up with these speeds requires the development of specialized devices and algorithms.
The following paragraphs describes efforts made in related areas:
Software-based: Most software based techniques concentrate on reducing the common case performance. Boyer-Moore [5] is a prime example of such a technique, as it lets its user search for strings in sub-linear time if the suffix of the string to be searched for appears rarely in the input stream.
While Boyer-Moore only searches for one string at a time, Fisk and Varghese [11] present a multiple-pattern search algorithm, that combines the one-pass approach of Aho-Corasick with the skipping feature of Boyer-Moore, as optimized for the average case by Horspool. The work by Tuck, et al. [20] takes a different approach to optimizing Aho-Corasick, by instead looking at bitmap compression and path compression to reduce the amount of memory needed.
Field Programmable Gate Array (FPGA)-based: The area that has seen the most amount of string matching research is in the reconfigurable computing community [8,13,16,12,3,4,7,10,6,2]. Proponents of the work in this area argue intrusion detection is a perfect application of reconfigurable computing because it is computationally intensive, throughput oriented, and the rule sets change over time but only relatively slowly. Because FPGAs are inherently reconfigurable, the majority of prior work in this area focuses on efficient ways to map a given rule set down to a specialized circuit that implements the search. The configuration (the circuit implemented on the FPGA) is custom designed to take advantage of the nature of a given specific rule set, and any change to the rule set will require the generation of a new circuit (usually in a hardware description language) which is then compiled down through the use of Computer Aided Design (CAD) tools.
The work of Sourdis and Pnevmatikatos [16] describes an approach that is specifically tuned to the hardware resource available to devices, available from Xilinx, to provide near optimal resource utilization and performance. Because Sourdis and Pnevmatikatos [16] demonstrate that their mapping is highly efficient, and they compare against prior work in the domain of reconfigurable computing, the present invention compares directly against their approach. Even though every shift-register and logic unit is being used in a highly efficient manner, the density and regularity of SRAM are used to a significant advantage in our approach, resulting in silicon level efficiencies of 10 times greater or more. It should be also noted that most FPGA based approaches are usually truly tied to an FPGA based implementation, because they rely on the underlying reconfigurability to adjust to new rule sets. In our approach, this is provided simply by updating the SRAM, and can be done in a manner that does not require a temporary loss of service.
What is needed, then, is an improved method of pattern matching over high-throughput network traffic. The present invention satisfies this need. The utility of this invention is that it provides a way to maintain tight bounds on worst case performance, allows updates with new rules without interrupting operation, and enables an order of magnitude increase in efficiency over prior art. This is potentially of interest to any producer of high throughput network devices.